import java.util.*;


 class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}


class Partition {
    public ListNode partition(ListNode pHead, int x) {

        ListNode head1 = null;
        ListNode head2 = null;
        ListNode cur1 = null;
        ListNode cur2 = null;
        ListNode cur = pHead;
        while (cur != null) {
            if (cur.val < x) {
                if (head1 == null) {
                    head1 = cur;
                    cur1 = cur;
                } else {
                    cur1.next = cur;
                    cur1 = cur1.next;
                }
            } else {
                if (head2 == null) {
                    head2 = cur;
                    cur2 = cur;
                } else {
                    cur2.next = cur;
                    cur2 = cur2.next;
                }
            }
            cur = cur.next;
        }
        if (head1 == null) {
            return head2;
        }
        cur1.next = head2;
        if(cur2!=null){
            cur2.next=null;
        }
        return head1;
    }
}

public class Text2 {
}
